﻿#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"

//堆排序
//排升序，建大堆
//排降序，建小堆
void Heapsort(int* arr, int n)
{
	//1.建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		Adjustdown(arr, n, i);
	}
	//此处花费n
	int end = n - 1;
	while (end>0)
	{
		swap(&arr[0], &arr[end]);
		//再次向下调整
		Adjustdown(arr, end, 0);//堆已经建好了，直接从根节点开始调整就行
		end--;
	}	//此处花费logn

	//时间复杂度？
	//n*log2(n)
}

int main()
{
	DataType arr[] = { 27,15,19,18,28,34,65,49,37,1,5,6,4,2,3,9,8,7 };
	//这个堆的左右子树都是小根堆，只有根节点不是,使用向下调整算法
	int n = sizeof(arr) / sizeof(arr[0]);
	//Heap hp;
	//HeapInit(&hp, arr, n);
	//for (int i = 0; i < n; i++)
	//{
	//	cout << hp.arr[i] << " ";
	//}
	//HeapPush(&hp, 1);
	Heapsort(arr, n);
	for (int i = 0; i < n; i++)
	{
		cout <<arr[i] << " ";
	}



}








//堆，用数组表示完全二叉树。二叉树的根就是堆的堆顶
//大根堆，每个父亲结点的值大于孩子结点。最大值是根节点
//小根堆，每个孩子结点的值大于父亲结点。最小值是根节点